/**
 *  @file PrintAndFreeInOrder.c
 *  @desc 按递增次序输出单链表中各节点的数据元素，并释放节点所占的存储空间（不使用数组）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-04 11:15
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// 定义链表结点结构
typedef struct node {
    int data;             // 数据域
    struct node *next;    // 指向下一个结点的指针
} node, *link;

// 创建一个新的结点并返回指针
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;  // 分配内存失败处理
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 向链表尾部插入一个结点（尾插法）
void insertTail(link *head, int value) {
    link newNode = createNode(value);  // 创建新结点
    if (newNode == NULL) return;       // 如果创建失败则退出
    if (*head == NULL) {
        // 如果链表为空，新结点作为头结点
        *head = newNode;
        return;
    }
    // 遍历找到链表末尾
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;  // 插入到末尾
}

// 打印链表中所有结点的数据（用于调试）
void printList(link head) {
    if (head == NULL) return;
    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 按递增顺序输出链表中的数据，并释放每个结点的内存
 * @note 该函数不使用任何辅助数组空间，采用每次遍历找最小值的方式
 * @param head 指向链表头指针的指针（为了在函数中修改头指针）
 */
void printAndFreeInOrder(link *head) {
    if (*head == NULL) return;  // 链表为空直接返回

    // 重复操作直到链表为空
    while (*head != NULL) {
        link cur = *head;       // 当前结点指针

        link minPre = NULL;     // 最小值结点的前驱
        link minNode = cur;     // 最小值结点，初始为第一个结点

        // 遍历链表找最小值结点及其前驱
        while (cur->next != NULL) {
            if (cur->next->data < minNode->data) {
                minPre = cur;
                minNode = cur->next;
            } else {
                cur = cur->next;
            }
        }

        // 输出最小值
        printf("value is %d\n", minNode->data);

        // 删除最小值结点，并更新链表指针
        if (minPre == NULL) {
            // 最小结点是头结点
            *head = minNode->next;
        } else {
            // 跳过最小值结点
            minPre->next = minNode->next;
        }

        // 释放该结点所占内存
        free(minNode);
    }
}

// 主函数：构造链表并调用处理函数
int main() {
    link head = NULL; // 初始化空链表

    // 插入几个测试数据
    insertTail(&head, 4);
    insertTail(&head, 2);
    insertTail(&head, 3);

    // 输出并释放链表中数据（按递增顺序）
    printAndFreeInOrder(&head);

    return 0;
}
